package pl.enigmatic.math.graph;

import static pl.enigmatic.math.graph.Tree.setParentChildRelationship;

import java.util.Comparator;
import java.util.HashSet;
import java.util.Set;

import pl.enigmatic.objects.WrapperObject;


public class Node<B, T extends Tree<B, T>> extends WrapperObject<B> implements Comparator<T> {

	/**
	 * The depth of <code>this</code> object in the tree structure. The same as the distance from the root of the tree <code>this</code> object
	 * belongs to.
	 */
	int depth = 0;

	/**
	 * The parent of <code>this</code> object in the tree structure.
	 */
	T parent = null;

	/**
	 * The root of the tree structure <code>this</code> object belongs to.
	 */
	T root = null;

	public Node(final B base) {
		super(base);
	}

	/**
	 * Called when the parent of the visual object is changed.
	 * @param oldParent
	 */
	protected void onParentChanged(final T old) {}

	/**
	 * Sets a new parent for <code>this</code> object. Nothing happens if <code>this</code> is an ancestor of the given new <code>parent</code>, or if
	 * the new <code>parent</code> is actually the same as the old one.
	 * @param parent the new <code>parent</code> for <code>this</code> object
	 * @return the index <code>this</code> has as a child in the children collection of the <code>parent</code>
	 */
	public int setParent(final T parent) {
		return setParentChildRelationship(parent, this, -1);
	}

	void setRoot(final T root) {
		this.root = root;
	}

	/** @return the tree parent of <code>this</code> object */
	public T getParent() {
		return parent;
	}

	public T getRoot() {
		return root;
	}

	public boolean hasParent() {
		return parent != null;
	}

	/**
	 * @return the depth
	 */
	public int getDepth() {
		return depth;
	}

	public int getIndex() {
		return hasParent() ? -1 : parent.getIndexOf(this);
	}

	/**
	 * Determines whether <code>this</code> object is a descendant of the <code>ancestor</code> object.
	 * @param ancestor object to check the relation on
	 * @return <code>true</code> if <code>this</code> object is a descendant of the <code>ancestor</code> object, otherwise - <code>false</code>
	 */
	public boolean isDescendantOf(final T ancestor) {
		return ancestor != null && ancestor.isAncestorOf(this);
	}

	/**
	 * @param depth the depth of the ancestor to find
	 * @return the ancestor of <code>this</code> object at a given depth if one exists, otherwise - <code>null</code>.
	 */
	public T findAncestor(final int depth) {
		if (hasParent() && 0 <= depth && depth <= parent.getDepth()) {
			T res = parent;
			while (depth < res.getDepth()) {
				res = res.getParent();
			}
			return res;
		}
		return null;
	}

	/**
	 * @param other the other object to find a common ancestor with
	 * @return the common ancestor of <code>this</code> object and <code>other</code> if one exists, otherwise - <code>null</code> .
	 */
	public T findCommonAncestor(final Node<B, T> other) {
		T left = null, right = null;
		if (hasParent() && other != null && other.hasParent() && root == other.root) {
			left = getParent();
			right = other.getParent();
			if (right.getDepth() > left.getDepth()) {
				right = right.findAncestor(left.getDepth());
			} else {
				left = left.findAncestor(right.getDepth());
			}
			while (left != right) {
				left = left.getParent();
				right = right.getParent();
			}
		}
		return left;
	}

	@Override
	public int compare(T left, T right) {
		if (left == right) {
			return 0;
		} else if (left == null) {
			return -1;
		} else if (right == null) {
			return 1;
		} else {
			final T common = left.findCommonAncestor(right);
			if (common == null) {
				return 0;
			} else if (common == left) {
				return 1;
			} else if (common == right) {
				return -1;
			} else {
				final int depth = common.getDepth() + 1;
				left = left.findAncestor(depth);
				right = right.findAncestor(depth);
				return right.getIndex() - left.getIndex();
			}
		}
	}

	public static interface Condition<B, T extends Tree<B, T>> {

		public boolean isSatisfied(Node<B, T> node);
	}

	public T findAncestorSatisfying(final Tree.Condition<B, T> condition) {
		T t = parent;
		while (t != null) {
			if (condition.isSatisfied(t)) { return t; }
			t = t.getParent();
		}
		return null;
	}

	public Set<T> findAllAncestorsSatisfying(final Tree.Condition<B, T> condition) {
		final Set<T> set = new HashSet<T>();
		T t = parent;
		while (t != null) {
			if (condition.isSatisfied(t)) {
				set.add(t);
			}
			t = t.getParent();
		}
		return set;
	}

}
